package algorithm.easy;

import java.util.HashMap;
import java.util.Map;

public class Solution169 {
    //给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
    //输入：[2,2,1,1,1,2,2]
    //输出：2
    //输入：[3,2,3]
    //输出：3
    public static int majorityElement(int[] nums) {
       int count = 0;
       int maj = nums[0];
       for(int i=1;i<nums.length;i++){
           if(maj==nums[i]){
               count++;
           }else{
               count--;
               if(count==0){
                   maj = nums[i+1];
               }
           }
       }
       return maj;
        /*Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],map.get(nums[i])==null?0:map.get(nums[i])+1);
        }
        int maxValue = -1;
        int maxKey = -1;
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            maxValue = maxValue > entry.getValue()?maxValue:entry.getValue();
            maxKey = entry.getKey();
        }

        return maxKey;*/
    }

    public static void main(String[] args){
        int[] nums = {3,2,3};//{2,2,1,1,1,2,2};
        System.out.println(majorityElement(nums));
    }

}
